#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

//it takes up less space, when I resize vector.
const int alphabet = 'z' - 'A' + 1; // or just alphabet = 255 (255 == sizeof(char)) :)
const char startLetter = 'A'; // = 0, if alphabet = 255

class Node {
private:
    vector<Node*> childs;
    Node* parent;
    bool isLeaf;
    char pCh;
    //I can't delete parentChar, it's necessary for creating links. But words are output just for fun :) I don't want to store excess field 'int'.
    Node* link;
    //vector deleted :) it is no longer relevant :)
public:
    Node() : link(NULL), pCh(-1), parent(NULL), isLeaf(false) {
        childs.resize(alphabet, NULL);
    }

    void initParent() {
        parent = this;
        link = this;
    }

    void addString(const string& s) {
        Node* tmp = this;
        size_t sLength = s.length();
        for (size_t i = 0; i < sLength; ++i) {
            char c = s[i] - startLetter;
            if (tmp->childs[c] == NULL) {
                Node* node = new Node();
                node->parent = tmp;
                node->pCh = c;
                tmp->childs[c] = node;
            }
            tmp = tmp->childs[c];
        }
        tmp->isLeaf = true;
    }

    Node* getLink(Node* node = NULL) {
        if (node == NULL)
            node = this;
        //it's just my small test, if I will write something like this: "Node* node; node->getLink(); //<=> getLink(node);"
        // because I can't write "Node* getLink(Node* node = this) { ... }; "
        if (node->link == NULL)
            node->link = (node->parent->parent == node->parent) ? node->parent : goTo(node->pCh, getLink(node->parent));
        return node->link;
    }

    Node* goTo(char c, Node* node = NULL) {
        if (node == NULL)
            node = this;
        Node* curLink = getLink(node);
        node->link = curLink;
        if (curLink->isLeaf)
            printNode(curLink);
        // sorry for this :) but it is very chore to write a lot of if-else then return.
        // but I put brackets, so this priority should be clear for understanding.
        // I promise I will not write bad codes (like this) in production ;)
        return (node->childs[c] == NULL) ? ((node->parent->parent == node->parent) ? ((node->parent->childs[c] != NULL) ? goTo(c, node->parent) : node->parent) : goTo(c, curLink)) : node->childs[c];
        //node->parent->parent == node->parent  - it's my checker: if we stand in root or near it(1 step).
    }

    void searchStrings(const string& text) {
        Node* tmp = this;
        size_t textLength = text.length();
        for (size_t i = 0; i < textLength; ++i) {
            char c = text[i] - startLetter;
            tmp = goTo(c, tmp);       
            if (tmp->isLeaf) {
                printNode(tmp);
            }
        }
        while (true) {
            tmp = getLink(tmp);
            if (tmp->isLeaf) {
                printNode(tmp);
            } else
                break;
        }
    }

    void printNode(Node* node = NULL) {
        if (node == NULL)
            node = this;
        vector<char> outPut;
        while(node->parent != node) {
            outPut.push_back(node->pCh);
            node = node->parent;
        }
        if (node->pCh != -1)
            outPut.push_back(node->pCh);
        for (vector<char>::reverse_iterator it = outPut.rbegin(); it != outPut.rend(); ++it)
            cout << (char)(*it + startLetter);
        cout << endl;
    }

    ~Node() {
        for (size_t i = 0; i < childs.size(); ++i)
            if (childs[i] != NULL)
                delete(childs[i]);
    }
};

int main() {
    Node* trie = new Node();
    trie->initParent();
    ifstream ifile("in.txt");
    string text, subString;
    if (getline(ifile, text))
        while (getline(ifile, subString))
            if(!subString.empty())
                trie->addString(subString);
    trie->searchStrings(text);
    ifile.close();
    delete(trie);
    return 0;
}